A mesh communication network, also called a point-to-point communication network, is made up of a plurality of nodes connected to each other by one-way or two-way links. The network includes N nodes, where N is any definite integer. The network is consequently finite and closed.
In such a network, the conveyance of a message between a source node and a recipient node uses intermediate nodes to relay the message and is based on a routing mechanism.
In general, whatever the nature of the hardware layer of the considered network, the problem of the robustness of the conveyance arises once the network is based on such a routing mechanism.
In order not to lose all or part of the communication service when a breakdown of one or more nodes and/or a rupture of one or more links occurs, or indeed to allow a functional need to be taken into account corresponding to the absence of one or more nodes, the topology of the network must necessarily have a certain degree of connectivity.
The connectivity of the network is a structural response to the need for robustness when one or more nodes or links disappear.
Thus, to obtain a network that is robust with respect to the disappearance of any subset, howsoever constituted, of p−1 nodes, it is necessary and sufficient for the graph corresponding to the network to be a p-connected graph.
Such a network then continues to provide the communication service between all of the remaining nodes for any group of p−1 missing nodes.
One necessary (but not sufficient) condition for a graph to be p-connected is that each of its nodes has at least p neighboring nodes, i.e., for it to be connected by two-way links to p other nodes of the network.
The complexity of the network increases with the total number N of nodes and the degree of connectivity of the network, i.e., the number of links between the nodes.
In a complex network, the question of routing proves to be a difficult problem to address, inasmuch as it is necessary to account for random changes of the network, such as the disappearance of one or more nodes or links.
In fact, if the routing function is not correctly thought out, it may lead to the total or partial loss of the communication service between the remaining nodes after a modification of the network, even when the remaining nodes retain a total structural connectivity to each other, of a nature to allow maintenance of the communication service.
In this context, the invention aims to offset these problems.